In networking systems, routers and/or switches typically move packets of information from one of a number of input ports to one or more output ports. Referring now to FIG. 1, a block diagram of a conventional router/switch system arrangement is shown and indicated by the general reference character 100. Input Ports 1, 2, . . . N can connect to Packet Receive 102, which can send Packet Headers to Lookup Engine 104 and Packets (Data and Headers) to Packet Storage Unit 108. The packet storage unit can store the packet data and the locations of this packet data can be identified by packet “pointers.” Typically, only one copy of the packet data may be stored in the packet storage unit regardless of the packet type (e.g., unicast or multicast). Lookup Engine 104 can provide signals 110 to Transmit Queue Control 106. Signals 110 can include a packet type indication (e.g., unicast or multicast), a transmit port number, and/or a packet pointer, for example. Further, the packet type information can also include a Media Access Control Destination Address (MACDA), as only one example. Transmit Queue Control 106 can provide signals 112 to Packet Storage Unit 108, which can store data and control the selections to Output Ports 1, 2, . . . N. Signals 112 can include information such as a transmit enable, a packet pointer, and/or a transmit port number. In other words, Transmit Queue Control 106 can “schedule” or set an order of the packets to be transmitted for each output port in the system by indicating the packet pointer in signals 112.
A lookup function, such as may be implemented in Lookup Engine 104 or the like, can include a content addressable memory (CAM), but this approach may be relatively expensive. Another approach is to use a standard memory, such as static random-access memory (SRAM), with a direct indexing of the entries. However, because a typical key may be, for example, 60-bits wide, a 260 universe (i.e., 260 table entries) would be required and this approach may be impractical and/or cost-prohibitive. A more common approach is to use the standard memory as a hashing table, which essentially provides a “many-to-one” function so that the table size can be made substantially smaller and the overall system cost can be reduced.
Referring now to FIG. 2A and FIG. 2B, a conventional hashing approach will be described. In FIG. 2A, which is indicated by the general reference character 200, Hash Function 202 receives “k” and includes Cyclic Redundancy Code (CRC) Generation 204 to produce the function “c(k).” CRC is a commonly used hashing function. In FIG. 2B, which is indicated by the general reference character 250, Hash Table 252 can be indexed by c(k) as “addr=c(k),” for example. The hash table can include several fields, such as Key 254, Error Checking and Correcting (ECC) 256, and Attribute 258. As shown, “e(k)” can be the ECC code of “k” and this can be used to test if a stored key has been corrupted. The standard of corruption protection provided with this approach can include single-bit-error correction and double-bit-error detection (SECDED). The ECC field in the hash table can, in some applications, increase the memory width so that it is too large for readily available memory configurations. Thus, specialty memories, at increased cost, would likely be required. As an alternative, some applications may not use an ECC function, but this is not desirable because there would be no way of correcting the stored data if it has been unintentionally changed.
Consequently, what is needed is an enhanced hashing approach that does not include an ECC field in the hash table, but still maintains an ECC function.